package my.jwds.p47;

import java.io.IOException;
import java.util.*;

public class PermuteUnique {

    public static void main(String[] args) throws IOException {
        PermuteUnique obj = new PermuteUnique();
        System.out.println(obj.permuteUnique(new int[]{1,1,3}));
        System.out.println(new PermuteUnique.Solution().permuteUnique(new int[]{1,1,3}));
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        return permuteUnique(nums,new boolean[nums.length],new Integer[nums.length],0);
    }


    public List<List<Integer>> permuteUnique(int[] nums,boolean[]occupy,Integer[] row,int index) {
        List<List<Integer>> res = new ArrayList<>();
        if (index == row.length){
            res.add(Arrays.asList(Arrays.copyOf(row,row.length)));
            return res;
        }
        boolean[] numsUse = new boolean[21];
        for (int i = 0; i < nums.length; i++) {
            if (!occupy[i] && !numsUse[nums[i]+10]){
                row[index] = nums[i];
                numsUse[nums[i]+10] = true;
                occupy[i] = true;
                res.addAll(permuteUnique(nums,occupy,row,index+1));
                occupy[i] = false;
            }
        }

        return res;
    }

    static class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            int len = nums.length;
            List<List<Integer>> res = new ArrayList<>();
            if (len == 0) {
                return res;
            }

            // 排序（升序或者降序都可以），排序是剪枝的前提
            Arrays.sort(nums);

            boolean[] used = new boolean[len];
            // 使用 Deque 是 Java 官方 Stack 类的建议
            Deque<Integer> path = new ArrayDeque<>(len);
            dfs(nums, len, 0, used, path, res);
            return res;
        }

        private void dfs(int[] nums, int len, int depth, boolean[] used, Deque<Integer> path, List<List<Integer>> res) {
            if (depth == len) {
                res.add(new ArrayList<>(path));
                return;
            }

            for (int i = 0; i < len; ++i) {
                if (used[i]) {
                    continue;
                }

                // 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义
                // 写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择
                if (i > 0 && nums[i] == nums[i - 1] && !used[i-1]) {
                    continue;
                }

                path.addLast(nums[i]);
                used[i] = true;

                dfs(nums, len, depth + 1, used, path, res);
                // 回溯部分的代码，和 dfs 之前的代码是对称的
                used[i] = false;
                path.removeLast();
            }

        }
    }
}